#ifndef FREQUENT_SUBGRAPH_MINING_H_
#define FREQUENT_SUBGRAPH_MINING_H_

#include "graph_normalization.h"

namespace masugo
{

template<typename GraphType>
class frequent_subgraphs_mining
{
public:
	typedef graph_normalization<std::size_t, typename GraphType::VertexValue, typename GraphType::EdgeValue> gn;
	typedef typename gn::VertexKey VertexKey;
	typedef typename gn::VertexValue VertexValue;
	typedef typename gn::EdgeValue EdgeValue;
	typedef typename gn::FGraph FGraph;
	typedef typename gn::FTree FTree;
	typedef typename gn::RTree RTree;

	typedef std::size_t GraphNumber;

	struct FrequentSubtreeResult
	{
		FrequentSubtreeResult(const FTree& ftree, const std::deque<std::size_t>& occurences) :
			ftree(ftree),
			occurences(occurences),
			successors_count(0),
			associatives_count(0) {}

		FTree ftree;
		std::deque<GraphNumber> occurences;
		int successors_count;
		int associatives_count;
	};

	typedef std::map<std::string, FrequentSubtreeResult> FrequentSubtreeResultMap;

	struct MaximalFrequentSubgraphResult
	{
		MaximalFrequentSubgraphResult(const FGraph& fgraph, const std::deque<std::size_t>& occurences) : fgraph(fgraph), occurences(occurences) {}

		FGraph fgraph;
		std::deque<std::size_t> occurences;
	};

	typedef std::deque<MaximalFrequentSubgraphResult> MaximalFrequentSubgraphResultList;

	struct MiningResult
	{
		MiningResult(FrequentSubtreeResultMap frequent_subtrees, MaximalFrequentSubgraphResultList maximal_frequent_subgraphs, int running_time) :
			frequent_subtrees(frequent_subtrees),
			maximal_frequent_subgraphs(maximal_frequent_subgraphs),
			running_time(running_time) {}

		FrequentSubtreeResultMap frequent_subtrees;
		MaximalFrequentSubgraphResultList maximal_frequent_subgraphs;
		int running_time;
	};

	static MiningResult mine_frequent_subgraphs(const std::deque<GraphType>& graphs, const std::size_t min_support, const bool only_subtrees)
	{
		const unsigned long start_time=utilities::BlockTimer::get_tick_count();
		FrequentSubtreeResultMap frequent_subtrees_map;
		MaximalFrequentSubgraphResultList maximal_frequent_subgraphs;
		std::deque<EmbeddedTree> stack=construct_frequent_embedded_vertices(graphs, min_support);
		for(std::size_t i=0;i<stack.size();i++) { frequent_subtrees_map.insert(std::make_pair(stack[i].canonical_string(), FrequentSubtreeResult(stack[i].ftree, utilities::collect_map_keys(stack[i].support)))); }
		while(!stack.empty())
		{
			const EmbeddedTree& etree=stack.back();
			const OuterExtensionMap frequent_outer_extensions=construct_frequent_outer_extensions(etree, graphs, min_support);
			const GrowthResult growth=construct_new_bigger_frequent_embedded_trees(etree, frequent_outer_extensions, graphs, frequent_subtrees_map, min_support);

			{
				FrequentSubtreeResult& fsr=frequent_subtrees_map.find(etree.canonical_string())->second;
				fsr.successors_count=growth.successors_count;
				fsr.associatives_count=growth.associatives_count;
			}

			if(!only_subtrees && (growth.associatives_count==0))
			{
				const InnerExtensionMap frequent_inner_extensions=construct_frequent_inner_extensions(etree, graphs, min_support);
				if(frequent_inner_extensions.empty())
				{
					if(growth.successors_count==0) { maximal_frequent_subgraphs.push_back(MaximalFrequentSubgraphResult(etree.ftree, utilities::collect_map_keys(etree.support))); }
				}
				else
				{
					const MaximalFrequentSubgraphResultList embedded_tree_maximal_frequent_subgraphs=construct_maximal_frequent_subgraphs_for_embedded_tree(etree, frequent_outer_extensions, frequent_inner_extensions, min_support);
					maximal_frequent_subgraphs.insert(maximal_frequent_subgraphs.end(), embedded_tree_maximal_frequent_subgraphs.begin(), embedded_tree_maximal_frequent_subgraphs.end());
				}
			}

			stack.pop_back();
			for(std::size_t i=0;i<growth.constructed_etrees.size();i++)
			{
				const EmbeddedTree& descendant_etree=growth.constructed_etrees[i];
				frequent_subtrees_map.insert(std::make_pair(descendant_etree.canonical_string(), FrequentSubtreeResult(descendant_etree.ftree, utilities::collect_map_keys(descendant_etree.support))));
				stack.push_back(descendant_etree);
			}
		}
		return MiningResult(frequent_subtrees_map, maximal_frequent_subgraphs, utilities::BlockTimer::get_tick_count()-start_time);
	}

private:
	typedef typename GraphType::VertexKey VertexKeyInData;

	typedef std::deque<VertexKeyInData> EmbeddingMapping;
	typedef std::deque<EmbeddingMapping> EmbeddingMappingList;
	typedef std::map<GraphNumber, EmbeddingMappingList> EmbeddingSupport;

	typedef std::size_t MappingNumber;

	typedef std::pair<VertexKey, std::pair<EdgeValue, VertexValue> > OuterExtension;
	typedef std::deque< std::pair<MappingNumber, VertexKeyInData> > OuterExtensionDirections;
	typedef std::map<GraphNumber, OuterExtensionDirections> OuterExtensionSupport;
	typedef std::map<OuterExtension, OuterExtensionSupport> OuterExtensionMap;

	struct EmbeddedTree
	{
		EmbeddedTree(const FTree& ftree, const EmbeddingSupport& support) :
			ftree(ftree),
			rtree(gn::construct_tree_canonical_form(ftree)),
			support(support)
		{
		}

		EmbeddedTree(const FTree& ftree, const RTree& rtree, const EmbeddingSupport& support) :
			ftree(ftree),
			rtree(rtree),
			support(support)
		{
		}

		std::string canonical_string() const { return rtree.canonical_string(); }

		std::size_t size() const { return ftree.vertices().size(); }

		FTree ftree;
		RTree rtree;
		EmbeddingSupport support;
	};

	struct GrowthResult
	{
		GrowthResult() : successors_count(0), associatives_count(0) {}
		int successors_count;
		int associatives_count;
		std::deque<EmbeddedTree> constructed_etrees;
	};

	typedef std::pair< std::pair<VertexKey, VertexKey>, EdgeValue > InnerExtension;
	typedef std::map< GraphNumber, std::set<MappingNumber> > InnerExtensionSupport;
	typedef std::map<InnerExtension, InnerExtensionSupport> InnerExtensionMap;

	static std::deque<EmbeddedTree> construct_frequent_embedded_vertices(const std::deque<GraphType>& graphs, const std::size_t min_support)
	{
		typedef std::map<VertexValue, EmbeddingSupport> LabeledVertexSupportMap;
		LabeledVertexSupportMap labeled_vertex_support_map;
		for(std::size_t i=0;i<graphs.size();i++)
		{
			const GraphType& graph=graphs[i];
			for(typename GraphType::Vertices::const_iterator it=graph.vertices().begin();it!=graph.vertices().end();it++)
			{
				labeled_vertex_support_map[it->second.value][i].push_back(EmbeddingMapping(1, it->first));
			}
		}
		std::deque<EmbeddedTree> frequent_embedded_vertices;
		for(typename LabeledVertexSupportMap::const_iterator it=labeled_vertex_support_map.begin();it!=labeled_vertex_support_map.end();it++)
		{
			if(it->second.size()>=min_support)
			{
				FTree ftree;
				ftree.set_vertex_value(0, it->first);
				frequent_embedded_vertices.push_back(EmbeddedTree(ftree, it->second));
			}
		}
		return frequent_embedded_vertices;
	}

	static OuterExtensionMap construct_frequent_outer_extensions(const EmbeddedTree& etree, const std::deque<GraphType>& graphs, const std::size_t min_support)
	{
		const std::deque<VertexKey> extension_frontier=etree.rtree.unique_frontier();
		OuterExtensionMap all_outer_extensions;
		for(typename EmbeddingSupport::const_iterator it=etree.support.begin();it!=etree.support.end();it++)
		{
			const GraphNumber graph_id=it->first;
			const EmbeddingMappingList& mapping_list=it->second;
			for(std::size_t i=0;i<mapping_list.size();i++)
			{
				const EmbeddingMapping& mapping=mapping_list[i];
				std::set<VertexKeyInData> forbidden_children;
				for(std::size_t j=0;j<mapping.size();j++) { forbidden_children.insert(mapping[j]); }
				for(std::size_t k=0;k<extension_frontier.size();k++)
				{
					std::size_t j=extension_frontier[k];
					const typename GraphType::Vertex& parent_vertex=graphs[graph_id].vertex(mapping[j]);
					for(typename GraphType::Vertex::Adjacency::const_iterator jt=parent_vertex.adjacency.begin();jt!=parent_vertex.adjacency.end();jt++)
					{
						const VertexKeyInData& child_key=jt->first;
						if(forbidden_children.find(child_key)==forbidden_children.end())
						{
							const OuterExtension oe=std::make_pair(j, std::make_pair(jt->second, graphs[graph_id].vertex(child_key).value));
							all_outer_extensions[oe][graph_id].push_back(std::make_pair(i, child_key));
						}
					}
				}
			}
		}
		OuterExtensionMap frequent_outer_extensions;
		for(typename OuterExtensionMap::const_iterator it=all_outer_extensions.begin();it!=all_outer_extensions.end();it++)
		{
			if(it->second.size()>=min_support) { frequent_outer_extensions.insert(*it); }
		}
		return frequent_outer_extensions;
	}

	template<typename Database>
	static GrowthResult construct_new_bigger_frequent_embedded_trees(const EmbeddedTree& etree, const OuterExtensionMap& frequent_outer_extensions, const std::deque<GraphType>& graphs, const Database& database, const std::size_t min_support)
	{
		GrowthResult results;
		results.successors_count=frequent_outer_extensions.size();
		results.associatives_count=0;
		for(typename OuterExtensionMap::const_iterator it=frequent_outer_extensions.begin();it!=frequent_outer_extensions.end();it++)
		{
			const OuterExtension& candidate=it->first;
			const OuterExtensionSupport& candidate_support=it->second;
			const VertexKey new_key=etree.ftree.vertices().size();
			FTree ftree=etree.ftree;
			ftree.set_vertex_value(new_key, candidate.second.second);
			ftree.connect(candidate.first, new_key, candidate.second.first);
			const RTree rtree=gn::construct_tree_canonical_form(ftree);
			if(database.find(rtree.canonical_string())==database.end())
			{
				EmbeddingSupport support;
				std::size_t full_current_mappings_use_count=0;
				for(typename OuterExtensionSupport::const_iterator jt=candidate_support.begin();jt!=candidate_support.end();jt++)
				{
					const GraphNumber graph_id=jt->first;
					const OuterExtensionDirections& directions=jt->second;
					const EmbeddingMappingList& current_mappings=etree.support.find(graph_id)->second;
					EmbeddingMappingList new_mappings;
					std::set<std::size_t> used_current_mappings;
					for(std::size_t i=0;i<directions.size();i++)
					{
						EmbeddingMapping mapping=current_mappings[directions[i].first];
						used_current_mappings.insert(directions[i].first);
						mapping.push_back(directions[i].second);
						new_mappings.push_back(mapping);
					}
					support[graph_id]=new_mappings;
					if(used_current_mappings.size()==current_mappings.size()) { full_current_mappings_use_count++; }
				}
				if(full_current_mappings_use_count==candidate_support.size()) { results.associatives_count++; }
				results.constructed_etrees.push_back(EmbeddedTree(ftree, rtree, support));
			}
		}
		return results;
	}

	static bool check_embedded_tree(const EmbeddedTree& etree, const std::deque<GraphType>& graphs, const std::size_t min_support)
	{
		if(etree.support.size()<min_support) { return false; }
		const typename FTree::Edges edges=etree.ftree.collect_edges();
		if(edges.size()+1!=etree.ftree.vertices().size()) { return false; }
		for(typename EmbeddingSupport::const_iterator it=etree.support.begin();it!=etree.support.end();it++)
		{
			const std::size_t graph_id=it->first;
			const EmbeddingMappingList& mappings=it->second;
			if(mappings.empty()) { return false; }
			for(std::size_t i=0;i<mappings.size();i++)
			{
				const EmbeddingMapping& mapping=mappings[i];
				if(mapping.size()!=etree.ftree.vertices().size()) { return false; }
				std::set<VertexKeyInData> mapping_set;
				for(std::size_t j=0;j<mapping.size();j++) { mapping_set.insert(mapping[j]); }
				if(mapping_set.size()!=mapping.size()) { return false; }
				for(std::size_t j=0;j<edges.size();j++)
				{
					const typename FTree::Edge& edge=edges[j];
					if(etree.ftree.vertex(edge.second.first).value!=graphs[graph_id].vertex(mapping[edge.second.first]).value) { return false; }
					if(etree.ftree.vertex(edge.second.second).value!=graphs[graph_id].vertex(mapping[edge.second.second]).value) { return false; }
					if(!graphs[graph_id].connected(mapping[edge.second.first], mapping[edge.second.second])) { return false; }
					if(edge.first!=graphs[graph_id].connection_value(mapping[edge.second.first], mapping[edge.second.second])) { return false; }
				}
			}
		}
		return true;
	}

	static InnerExtensionMap construct_frequent_inner_extensions(const EmbeddedTree& etree, const std::deque<GraphType>& graphs, const std::size_t min_support)
	{
		if(etree.size()<3) { return InnerExtensionMap(); }
		const std::deque<VertexKey> unique_frontier=etree.rtree.unique_frontier();
		InnerExtensionMap all_inner_extensions;
		for(typename EmbeddingSupport::const_iterator it=etree.support.begin();it!=etree.support.end();it++)
		{
			const GraphNumber graph_id=it->first;
			const EmbeddingMappingList& mapping_list=it->second;
			for(std::size_t i=0;i<mapping_list.size();i++)
			{
				const EmbeddingMapping& mapping=mapping_list[i];
				std::map<VertexKeyInData, std::size_t> reverse_mapping;
				for(std::size_t j=0;j<mapping.size();j++) { reverse_mapping[mapping[j]]=j; }
				for(std::size_t k=0;k<unique_frontier.size();k++)
				{
					const VertexKey j=unique_frontier[k];
					const typename GraphType::Vertex& parent_vertex=graphs[graph_id].vertex(mapping[j]);
					for(typename GraphType::Vertex::Adjacency::const_iterator jt=parent_vertex.adjacency.begin();jt!=parent_vertex.adjacency.end();jt++)
					{
						VertexKeyInData child_key=jt->first;
						typename std::map<typename GraphType::VertexKey, std::size_t>::const_iterator kt=reverse_mapping.find(child_key);
						if(kt!=reverse_mapping.end() && j<kt->second && !etree.ftree.connected(j, kt->second))
						{
							const InnerExtension ie=std::make_pair(std::make_pair(j, kt->second), jt->second);
							all_inner_extensions[ie][graph_id].insert(i);
						}
					}
				}
			}
		}
		InnerExtensionMap frequent_inner_extensions;
		for(typename InnerExtensionMap::const_iterator it=all_inner_extensions.begin();it!=all_inner_extensions.end();it++)
		{
			if(it->second.size()>=min_support) { frequent_inner_extensions.insert(*it); }
		}
		return frequent_inner_extensions;
	}

	static std::set<InnerExtension> collect_associative_inner_extensions(const EmbeddedTree& etree, const InnerExtensionMap& frequent_inner_extensions)
	{
		std::set<InnerExtension> associative_inner_extensions;
		for(typename InnerExtensionMap::const_iterator it=frequent_inner_extensions.begin();it!=frequent_inner_extensions.end();it++)
		{
			const InnerExtension& edge=it->first;
			const InnerExtensionSupport& support=it->second;
			bool associative=(support.size()==etree.support.size());
			for(InnerExtensionSupport::const_iterator jt=support.begin();jt!=support.end() && associative;jt++)
			{
				const GraphNumber graph_id=jt->first;
				associative=(etree.support.find(graph_id)->second.size()==jt->second.size());
			}
			if(associative) { associative_inner_extensions.insert(edge); }
		}
		return associative_inner_extensions;
	}

	static InnerExtensionSupport intersect_two_inner_extension_supports(const InnerExtensionSupport& support1, const InnerExtensionSupport& support2)
	{
		InnerExtensionSupport intersection;
		const InnerExtensionSupport& s1=(support1.size()<support2.size() ? support1 : support2);
		const InnerExtensionSupport& s2=(support1.size()<support2.size() ? support2 : support1);
		for(InnerExtensionSupport::const_iterator it1=s1.begin();it1!=s1.end();it1++)
		{
			for(std::set<std::size_t>::const_iterator jt1=it1->second.begin();jt1!=it1->second.end();jt1++)
			{
				InnerExtensionSupport::const_iterator it2=s2.find(it1->first);
				if(it2!=s2.end() && it2->second.find(*jt1)!=it2->second.end())
				{
					intersection[it1->first].insert(*jt1);
				}
			}
		}
		return intersection;
	}

	static bool match_inner_extension_support_with_outer_extension_map(const InnerExtensionSupport& inner_extension_support, const OuterExtensionMap& outer_extension_map, const std::size_t min_support)
	{
		for(typename OuterExtensionMap::const_iterator it=outer_extension_map.begin();it!=outer_extension_map.end();it++)
		{
			const OuterExtensionSupport& outer_extension_map_support=it->second;
			std::size_t matches_count=0;
			for(typename OuterExtensionSupport::const_iterator jt=outer_extension_map_support.begin();jt!=outer_extension_map_support.end() && (matches_count<min_support);jt++)
			{
				const GraphNumber graph_id=jt->first;
				const OuterExtensionDirections& directions=jt->second;
				InnerExtensionSupport::const_iterator kt=inner_extension_support.find(graph_id);
				if(kt!=inner_extension_support.end())
				{
					const std::set<MappingNumber>& mappings_set=kt->second;
					bool found_match=false;
					for(std::size_t i=0;i<directions.size() && !found_match;i++)
					{
						found_match=mappings_set.find(directions[i].first)!=mappings_set.end();
					}
					if(found_match)
					{
						matches_count++;
						if(matches_count>=min_support) { return true; }
					}
				}
			}
		}
		return false;
	}

	static FGraph apply_inner_extensions_on_embedded_tree(const EmbeddedTree& etree, const std::set<InnerExtension>& inner_extensions)
	{
		FGraph fgraph=etree.ftree;
		for(typename std::set<InnerExtension>::const_iterator it=inner_extensions.begin();it!=inner_extensions.end();it++)
		{
			fgraph.connect(it->first.first, it->first.second, it->second);
		}
		return fgraph;
	}

	static std::string construct_inner_extensions_string_representation(const std::set<InnerExtension>& inner_extensions)
	{
		std::ostringstream output;
		for(typename std::set<InnerExtension>::const_iterator it=inner_extensions.begin();it!=inner_extensions.end();it++)
		{
			output << "(" << it->first.first << "," << it->first.second << "," << it->second << ")";
		}
		return output.str();
	}

	static bool match_graph_equivalence_classes(const FGraph& fgraph1, const FGraph& fgraph2)
	{
		return (gn::construct_graph_maximal_spanning_tree_string(fgraph1)==gn::construct_graph_maximal_spanning_tree_string(fgraph2));
	}

	static MaximalFrequentSubgraphResultList construct_maximal_frequent_subgraphs_for_embedded_tree(const EmbeddedTree& etree, const OuterExtensionMap& outer_extensions, const InnerExtensionMap& frequent_inner_extensions, const std::size_t min_support)
	{
		MaximalFrequentSubgraphResultList result;
		if(!frequent_inner_extensions.empty())
		{
			const std::set<InnerExtension> associative_inner_extensions=collect_associative_inner_extensions(etree, frequent_inner_extensions);
			if(associative_inner_extensions.empty() || match_graph_equivalence_classes(etree.ftree, apply_inner_extensions_on_embedded_tree(etree, associative_inner_extensions)))
			{
				std::deque< std::pair<std::set<InnerExtension>, InnerExtensionSupport> > stack;

				if(associative_inner_extensions.empty())
				{
					for(typename InnerExtensionMap::const_iterator it=frequent_inner_extensions.begin();it!=frequent_inner_extensions.end();it++)
					{
						std::set<InnerExtension> inner_extensions;
						inner_extensions.insert(it->first);
						stack.push_back(std::make_pair(inner_extensions, it->second));
					}
				}
				else
				{
					InnerExtensionSupport associative_inner_extensions_support;
					for(typename std::set<InnerExtension>::const_iterator it=associative_inner_extensions.begin();it!=associative_inner_extensions.end();it++)
					{
						if(associative_inner_extensions_support.empty()) { associative_inner_extensions_support=frequent_inner_extensions.find(*it)->second; }
						else { associative_inner_extensions_support=intersect_two_inner_extension_supports(associative_inner_extensions_support, frequent_inner_extensions.find(*it)->second); }
					}
					stack.push_back(std::make_pair(associative_inner_extensions, associative_inner_extensions_support));
				}

				std::set<std::string> processed_sets;
				while(!stack.empty())
				{
					const std::pair<std::set<InnerExtension>, InnerExtensionSupport> parent=stack.back();
					stack.pop_back();
					int successors_count=0;
					for(typename InnerExtensionMap::const_iterator it=frequent_inner_extensions.begin();it!=frequent_inner_extensions.end();it++)
					{
						const InnerExtension& ie=it->first;
						if(parent.first.find(ie)==parent.first.end())
						{
							std::set<InnerExtension> child_inner_extensions=parent.first;
							child_inner_extensions.insert(ie);
							const std::string child_string_representation=construct_inner_extensions_string_representation(child_inner_extensions);
							if(processed_sets.find(child_string_representation)==processed_sets.end())
							{
								const InnerExtensionSupport child_support=intersect_two_inner_extension_supports(parent.second, it->second);
								if(child_support.size()>=min_support)
								{
									successors_count++;
									stack.push_back(std::make_pair(child_inner_extensions, child_support));
									processed_sets.insert(construct_inner_extensions_string_representation(child_inner_extensions));
								}
							}
							else
							{
								successors_count++;
							}
						}
					}
					if(successors_count==0
							&& !match_inner_extension_support_with_outer_extension_map(parent.second, outer_extensions, min_support)
							&& match_graph_equivalence_classes(etree.ftree, apply_inner_extensions_on_embedded_tree(etree, parent.first)))
					{
						result.push_back(MaximalFrequentSubgraphResult(apply_inner_extensions_on_embedded_tree(etree, parent.first), utilities::collect_map_keys(parent.second)));
						if(parent.first.size()==frequent_inner_extensions.size()) { stack.clear(); }
					}
				}
			}
		}
		return result;
	}
};

}

#endif /* FREQUENT_SUBGRAPH_MINING_H_ */
